// https://leetcode-cn.com/problems/palindromic-substrings/

class Solution {
public:
    bool isPalin(string s) {
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            if (s[l] != s[r]) return false;
        }
        return true;
    }
    int countSubstrings(string s) {
        int n = s.length();
        if (s.empty()) return 0;
        // vector<int> res(n, 0);
        // res[0] = 1;
        // for (int i = 0; i < n; ++i) {
        //     for (int j = 0; j < i; ++j) {
        //         if (isPalin(s.substr(j + 1, i - j))) {
        //             res[i] = max(res[i], res[j] + 1);
        //         }                
        //     }
        // }
        // return res[n - 1];
        // 不可以这样dp，可能res[j]中的元素和后面一起构成回文子串

        // 区间型dp
        // vector<vector<int>> res(n, vector<int>(n, 0)); // res[i][j]表示i到j之间回文子串的个数
        // res[0][0] = 1;
        // for (int i = 1; i < n; ++i) {
        //     res[i][i] = 1;
        //     res[i - 1][i] = 2 + s[i - 1] == s[i];
        // }
        // for (int len = 3; len <= n; ++len) {
        //     for (int i = 0; i < n - len + 1; ++i) {
        //         res[i][i + len - 1] = res[i + 1][i + len - 2] + 2 + (s[i] == s[i + len - 1]);
        //     }
        // }
        // return res[0][n - 1];
        // 这样还是会有漏的，不只是加两个边界，可能边界和中间组成了回文
        // 输入："aaa" 输出：4 预期结果：6

        // https://leetcode-cn.com/problems/palindromic-substrings/solution/liang-dao-hui-wen-zi-chuan-de-jie-fa-xiang-jie-zho/
        // dp[i][j]i到j是否回文子串，用ans来计数
        vector<vector<bool>> res(n, vector<bool>(n, false)); 
        int ans = 1;
        res[0][0] = true;
        for (int i = 1; i < n; ++i) {
            res[i][i] = true;
            ans++;
            if(s[i - 1] == s[i]) {
                res[i - 1][i] = true;
                ans++;
            }
        }
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i < n - len + 1; ++i) {
                res[i][i + len - 1] = res[i + 1][i + len - 2] && (s[i] == s[i + len - 1]);
                if (res[i][i + len - 1]) ans++;
            }
        }
        return ans;
    }
};

// 法二：枚举中心点，向两边扩散
class Solution {
public:
    int getPalin(string s, int i, int j) {
        int ans = 0;
        while (i >= 0 && j < s.length()) {
            if (s[i] != s[j]) break; 
            i--;
            j++;
            ans++;
        }
        i++;
        return ans;
    }
    int countSubstrings(string s) {
        int n = s.length();
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            ans += getPalin(s, i, i);
            if (s[i] == s[i - 1]) {
                ans += getPalin(s, i - 1, i);
            }
        }
        return ans;
    }
};